import java.util.Comparator;
import java.util.TreeMap;
import java.util.PriorityQueue;

public class LeetCode347WithJCF {
//    private class Freq{
//        public int e,freq;

//        public Freq(int e, int freq) {
//            this.e = e;
//            this.freq = freq;
//        }

//        @Override
//        public int compareTo(Freq another) {
//            if (this.freq < another.freq){
//                return -1;
//            } else if (this.freq > another.freq) {
//                return 1;
//            }
//            return 0;
//        }
//    }

    // 比较器，下面改造为匿名内部类
//    private class FreqComparator implements Comparator<Freq>{
//
//        @Override
//        public int compare(Freq a, Freq b) {
//            return a.freq - b.freq;
//        }
//    }

    public int[] topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (int num:nums) {
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }
//        PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
        // 使用匿名内部类重写compare方法
//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer a, Integer b) {
//                return map.get(a)-map.get(b);
//            }
//        });
        // 使用Lambda表达式改写
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a,b) -> map.get(a)-map.get(b)
        );
        for (int key:map.keySet()){
            if (pq.size() < k){
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.remove();
        }

        return res;
    }

}
